import bisect


class SnapshotArray(object):

    def __init__(self, length):
        """
        :type length: int
        """
        self.nap = 0
        self.d = [[] for _ in range(length)]

    def set(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        self.d[index].append([self.nap, val])

    def snap(self):
        """
        :rtype: int
        """
        self.nap += 1
        return self.nap - 1

    def get(self, index, snap_id):
        """
        :type index: int
        :type snap_id: int
        :rtype: int
        """
        r_index = bisect.bisect_right(self.d[index], [snap_id, 10 ** 9 + 7])
        if r_index == 0:
            return 0
        else:
            return self.d[index][r_index - 1][1]
